#include <dbg.h>
#include <gtest/gtest.h>
using namespace std;

class Solution {
public:
    long long countPairs(int n, vector<vector<int>>& edges) {
        // 建图
        vector<vector<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        dbg(graph);

        vector<bool> visited(n, false);

        long long res = 0;
        // 设当前连通块的大小为 size, total 维护前面求出的连通块的大小之和
        for (int i = 0, total = 0; i < n; i++) {
            if (!visited[i]) {  // 未访问的点：说明找到了一个新的连通块
                int size = dfs(i, graph, visited);
                // 连通块中的每个点，与前面遍历过的连通块的每个点，都是无法互相到达的
                res += (long)size *
                       total;  // 根据乘法原理，这有 size⋅total 个，加到答案中
                total += size;
                dbg(size, total);
            }
        }
        return res;
    }

private:
    int dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
        visited[node] = true;  // 标记为已访问

        int size = 1;                       // 当前节点的大小
        for (int neighbor : graph[node]) {  // 遍历当前节点的所有邻居节点
            if (!visited[neighbor]) {
                size += dfs(neighbor, graph, visited);  // 递归访问邻居节点
            }
        }
        return size;
    }
};

TEST(TEST1, countPairs) {
    Solution s;

    vector<vector<int>> edges{{0, 1}, {0, 2}, {1, 2}};
    EXPECT_EQ(s.countPairs(3, edges), 0);
}

TEST(TEST2, countPairs) {
    Solution s;

    vector<vector<int>> edges{{0, 2}, {0, 5}, {2, 4}, {1, 6}, {5, 4}};
    EXPECT_EQ(s.countPairs(7, edges), 14);
}

int main(int argc, char** argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}